package tree;

import java.util.ArrayList;
import java.util.List;

//二叉查找数
public class QueryTree extends Tree {

    public QueryTree(TreeNode root) {
        super( root );
    }

    public QueryTree() {

    }

    //增加节点
    //newNode 要新增的节点
    //oldNode 当前位置上的节点
    //新增的节点和当前位置上的节点进行比较，确定添加在左边还是右边
    //递归的执行效率低于循环
    public void addNode(TreeNode newNode,TreeNode oldNode){
        //判断大小关系
        if(newNode.getVal()<oldNode.getVal()){
            //判断当前节点的左边是否为空
            if (oldNode.getLeft()==null){
                oldNode.setLeft( newNode );
            }else{
                addNode(newNode, oldNode.getLeft() );
            }

        }else{
            if (oldNode.getRight()==null){
                oldNode.setRight(newNode);
            }else{
                addNode( newNode, oldNode.getRight() );
            }
        }
    }
    //查找次数
    public int count=0;
    //查询指定的值
    //与当前节点进行比较，等于就是找到了，小于就和左节点比较，大于就和右节点比较
    public void findVal(int num,TreeNode node){
        if (node==null){
            System.out.println("没有找到！ 查询次数是"+count+"次");
            return;
        }else{
            count++;
            if (num==node.getVal()){
                System.out.println("找到了！查询次数是"+count+"次");
                return;
            }else if (num<node.getVal()){
                //让该值和当前节点的左节点进行比较
                findVal( num, node.getLeft() );
            }else{
                findVal( num, node.getRight() );
            }

        }
    }

    public static void main(String[] args) {
        TreeNode t8= new TreeNode(8);
        QueryTree queryTree = new QueryTree(t8);


        TreeNode t0 = new TreeNode(0);
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t9 = new TreeNode(9);
        TreeNode t6 = new TreeNode(6);

        List<TreeNode> nodes = new ArrayList<TreeNode>();
        nodes.add(t0);
        nodes.add(t1);
        nodes.add(t2);
        nodes.add(t3);
        nodes.add(t4);
        nodes.add(t5);
        nodes.add(t9);
        nodes.add(t6);

        for (TreeNode node:nodes){
            queryTree.addNode(node,queryTree.getRoot());
        }
        //打印输出节点 (从小到大)
        //中
        queryTree.middle(queryTree.getRoot());
//        System.out.println();
//        queryTree.last(queryTree.getRoot());
//        System.out.println();
//        queryTree.first(queryTree.getRoot());

        queryTree.findVal( 9,queryTree.getRoot() );
    }
}
